We study the issue of data consistency in highly-available distributedsystems. Specifically, we consider a distributed system that replicates itsdata at multiple sites, which is prone to partitions, and which is expected tobe highly available. In such a setting, strong consistency, where all replicasof the system apply synchronously every operation, is not possible toimplement. However, many weaker consistency criteria that allow a greaternumber of behaviors than strong consistency, are implementable in distributedsystems. We focus on determining the strongest consistency criterion that can beimplemented in a distributed system that tolerates partitions. We show that nocriterion stronger than Monotonic Prefix Consistency (MPC) can be implemented.MPC is the consistency criterion underlying blockchains.
展开▼